/* 0. 代码随想录 */
// step 1# 创建一个新节点
struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// step 2# 主函数：构造最大二叉树
struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize) {
    if (numsSize == 0) return NULL;  // 边界条件：空数组返回 NULL

    // step 2.1# 找到数组中最大值及其下标
    int maxVal = INT_MIN;           // 初始化最大值为最小整数
    int maxIndex = 0;               // 初始化最大值下标
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > maxVal) {
            maxVal = nums[i];       // 更新最大值
            maxIndex = i;           // 更新最大值下标
        }
    }

    // step 2.2# 创建当前节点，并赋最大值
    struct TreeNode* root = createNode(maxVal);

    // step 2.3# 递归构造左子树（最大值左边的子数组）
    root->left = constructMaximumBinaryTree(nums, maxIndex);

    // step 2.4# 递归构造右子树（最大值右边的子数组）
    root->right = constructMaximumBinaryTree(nums + maxIndex + 1, numsSize - maxIndex - 1);

    // step 2.5# 返回当前构造的根节点
    return root;
}


/* 1. 20250421 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/*
    1. for 找最大值和下标
    2. 把最大值作为新节点创建 root
    3. 左子树递归：数组是 num，长度是 index 
    4. 右子树递归：数组是 num + index + 1， 长度是 numsSize - index - 1；
*/

typedef struct TreeNode TreeNode;

TreeNode *createNode(int val) {
    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

TreeNode *maxTree(int *nums, int numsSize) {
    if (numsSize <= 0) return NULL;
    
    int maxVal = INT_MIN;
    int maxIndex = -1;
    for(int i = 0; i < numsSize; i++) {
        if (nums[i] > maxVal) {
            maxVal = nums[i];
            maxIndex = i;
        }
    }

    TreeNode *curNode = createNode(maxVal);

    curNode->left = maxTree(nums, maxIndex);
    curNode->right = maxTree(nums + maxIndex + 1, numsSize - maxIndex - 1);

    return curNode;
}

struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize) {
    return maxTree(nums, numsSize);
}